/**
 * 860. 柠檬水找零
 * https://leetcode-cn.com/problems/lemonade-change/
 */
public class Solutions_860 {
    public static void main(String[] args) {
//        int[] nums = {5, 5, 5, 10, 20};  // output: true
//        int[] nums = {5, 5, 10};  // output: true
//        int[] nums = {10, 10};  // output: false
        int[] nums = {5, 5, 10, 10, 20};  // output: false

        boolean result = lemonadeChange(nums);
        System.out.println(result);
    }

    public static boolean lemonadeChange(int[] bills) {
        // 记录已有的不同面额的数量
        int five = 0, ten = 0, twenty = 0;

        for (int num : bills) {
            if (num == 5) {
                // 给 5 元时，不用找零
                five ++;
            } else if (num == 10) {
                // 给 10 元时，需要找零 5 元
                if (five < 1) {
                    return false;
                }
                ten ++;
                five --;
            } else if (num == 20) {
                // 给 20 元时，需要找零 15 元
                // 贪心思想，先判断有没有 10 元，如果有，那么可以找 1 张 10 元，1 张 5 元
                // 否则找零 3 张 5 元，无法找零时 return false
                if (ten >= 1 && five >= 1) {
                    twenty ++;
                    five --;
                    ten --;
                } else if (five >= 3) {
                    five -= 3;
                    twenty ++;
                } else {
                    return false;
                }
            }
        }
//        System.out.println("最终面额数量：");
//        System.out.println("5 元 " + five + " 张");
//        System.out.println("10 元 " + ten + " 张");
//        System.out.println("20 元 " + twenty + " 张");
        return true;
    }
}
